package pers.vic.basics.algorithm.monotone;

import org.omg.Messaging.SyncScopeHelper;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.concurrent.BlockingDeque;

/**
 * @description:找到左起第一个比当前数字小的元素
 * @author Vic.xu
 * @date: 2021/1/20 0020 16:28
 */
public class M_01 {

    public static void main(String[] args) {
        int[] nums = {3, 5, 4, 1};
        int[]  result = nextMin(nums);
        System.out.println(Arrays.toString(result));

        int[]  result2 = nextMax(nums);
        System.out.println(Arrays.toString(result2));
        System.out.println("123");
    }

    /**
     *下一个更小的数字
     * 单调递减栈
     * 只要当前数比栈顶中的数小 ，那就不能入栈，也说面栈顶的数的下一个更小的数字就是当前数
     */
    public  static int[] nextMin(int[] nums){
        int len = nums.length;
        int[] res =new int[len];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            int cur = nums[i];
            //当前数比栈里的数小 则当前数是栈里的数的下一个更小的数字
            while (!stack.isEmpty() && cur < nums[stack.peek()]) {
                res[stack.peek()] = cur;
                stack.pop();
            }
            //入栈
            stack.push(i);
        }
        return res;
    }

    /**
     * 下一个更大的数字
     * 单调递增栈 ，如果当前的数字比栈顶的数字大，那就说明 当前数字是栈顶的数字的下一个更大的数字
     */
    public  static int[] nextMax(int[] nums){
        int len = nums.length;
        int[] res =new int[len];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            int cur = nums[i];
            //当前数比栈顶大  则当前数就是栈顶数的下一个更大的数字
            while (!stack.isEmpty() && cur > nums[(stack.peek())]) {
                res[stack.peek()] = cur;
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }
}
